课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了VC维以及特征选择。

4 无限个假设（infinite $\mathcal H$）的情况

介绍之前给出一些定义。

给定集合$S =\{x^{(1)} ,…,x^{(d)}\}$，其中$x^{(i)} \in \mathcal X$，我们称$\mathcal H$打散（shatter）$S$如果$\mathcal H$能实现$S$上任意一种标签。即对任意标签集$\{y^{(1)} ,…,y^{(d)}\}$，存在$h\in \mathcal H$，使得$h(x^{(i)}) = y^{(i)}$。给定集合$\mathcal H$，定义其VC维（VapnikChervonenkis dimension）为$\mathcal H$能打散的最大的集合数量，用$\text{VC}(\mathcal H)$表示，如果$\mathcal H$能打散任意数量的集合，那么$\text{VC}(\mathcal H) =\infty$。

例如，考虑如下三个点的集合：

二维线性分类器$(h(x) = 1\{\theta_0 + \theta_1 x_1 + \theta_2 x_2 \ge 0\})$的假设类$\mathcal H $能否将上述情形打散呢？回答是肯定的，如下图所示：

此外，不难看出$\mathcal H$无法打散$4$个点的情形，所以$\text{VC}(\mathcal H) =3$。

需要注意的是，尽管$\text{VC}(\mathcal H) =3$，但仍然有$3$个点的情形无法被打散，如下图所示：

换句话说，在VC维的定义下，为了证明$\text{VC}(\mathcal H) $至少为$d$，只要证明至少有一个规模为$d$的集合能被打散即可。

接下来给出学习理论中的重要定理：

定理

给定$\mathcal H$，令$d = \text{VC}(\mathcal H) $，那么有至少$1-\delta$的概率，对于任意$h \in \mathcal H$，

因为，至少有$1-\delta$的概率，我们有：

换句话说，如果假设类的VC维有限，那么当$m$比较大的时候一致收敛就会成立，和之前一样，这就能让我们用$\epsilon(h^*)$的形式给出$\epsilon(h)$的上界。我们还有如下推论：

推论

为了让$|\epsilon(h) -\hat \epsilon (h)|\le \gamma$对于任意$h \in \mathcal H$有至少$1-\delta$的概率成立（从而可以推出$\epsilon (\hat h) \le \epsilon(h^*) +2\gamma$，只要满足$m=O_{\gamma,\delta}(d)$

换句话说，要使得假设类$\mathcal H$的表现比较好，我们需要和其VC维线性关系的数据，实际中，VC维往往和参数数量呈线性关系，所以一般情况下训练样本数要和参数数量呈线性关系。

备注：有关VC维的部分这里比较简略，可以参考林轩田老师的课程以及Learning From Data第二章的内容。

Part VII 正则化（Regularization ）与模型选择（model selection ）

这一讲主要介绍如何权衡偏差与方差，选择适合的模型以及参数。

1 交叉验证（Cross validation）

假设给定训练集$S$，我们已经了解经验风险最小化，来看下面一个使用经验风险最小化推导的算法：

  • 1.在$S$上训练每个模型$M_i$，得到假设$h_i$。
  • 2.选择具有最小训练误差的假设。

这个算法是没有用的。考虑选择多项式的次数，多项式次数越高，那么模型在训练集上的表现就越好，因此就有较小的训练误差。所以这个模型会选择一个有高方差，高次数的多项式模型，这通常是一个糟糕的选择。

现在有一个效果更好的算法，叫做保留交叉验证（hold-out cross validation），也叫做简单交叉验证（simple cross validation） ，步骤如下：

  • 1.将$S​$随机分为$S_{\text{train}}​$（一般为$70\%​$）和$S_{\text{cv}}​$（剩余的$30\%​$）。这里$S_{\text{cv}}​$被称为保留交叉验证集。
  • 在$S_{\text{train} }$训练每个模型$M_i$获得$h_i$。
  • 选择在交叉验证集上误差$\hat \epsilon_{S_{\text {cv}}}(h_i)​$最小的假设$h_i​$。（回顾，$\hat \epsilon_{S_{\text cv}}(h)​$表示$h​$在$S_{\text{cv}}​$上的经验风险）。

通过在我们没有训练过的样本$S_{\text{cv}}​$上做测试，我们得到了对$h_i​$的真实泛化误差的更好估计，而且可以选择具有最小泛化估计误差的假设。通常，交叉验证集合的比例选在$\frac 1 4 -\frac 1 3​$直接，$30\%​$是一个经典的选择。

另一种选择是，将步骤$3$替换为根据$\arg \min _i \hat \epsilon_{S_{\text cv}}(h_i)$选择模型$M_i$，然后在全体数据$S$上重新训练$M_i$。（这通常是一个好方法，除了学习算法对初始条件和数据的扰动非常敏感的情形，这时候，在$S_{\text{train}}$上表现很好的模型未必能在$S_{\text{cv}}​$表现很好，这时候最好取消重新训练的步骤。）

保留交叉验证的劣势在于保留交叉验浪费了$30\%$的数据，即使我们选择在全体数据上重新训练模型，我们仍然只是在$0.7m$的数据上找到表现最好的模型，因为我们每次只是在$0.7m$的数据上训练模型。当数据充足或者很廉价的时候这种方法没有问题，而当数据很少的时候，我们希望有更好的方法。

下面是一个方法，被称为$k$-折叠交叉验证（$k$-fold cross validation），每次保留的数据更少的数据：

  • 1.将$S$随机分为$k$个不相交的子集，每个子集有$m/k$个训练样本，称每个子集为$S_1,…,S_k$
  • 2.对每个模型$M_i$，我们按如下方式进行评估：
    • 对$j=1,…,k$
      • 在$S_1\bigcup…\bigcup S_{j-1}\bigcup S_{j+1}\bigcup …S_k$（即除了$S_j$以外的数据）训练$M_i$获得假设$h_{ij}$。在$S_j$上测试$h_{ij}$，得到$\hat \epsilon_{S_j}(h_{ij})$
    • 计算$\hat \epsilon_{S_j}(h_{ij})$的平均值来估计模型$M_i$的泛化误差
  • 3.选择具有最小泛化误差估计值的模型$M_i$，在$S$上重新训练模型，这样产生的假设是最终结果

$k$的经典选择是$10$。尽管每次验证的数据只有$1/k$（比之前少很多），但这个过程需要更多的计算成本，因为我们要对每个模型训练$k$次。

尽管$k=10$是一个常用的选择，在数据量非常少的时候，有时我们会选择$k=m$的极端情形，为了每次尽可能少的排除数据。在这种情况下，每次会在除了$S$中一个训练样本的数据上训练，在保留样本上测试，然后计算$m=k$个误差的平均值来估计模型的泛化误差。这种方法有自己的名字，因为我们每次保留一个训练数据，这种方法被称为弃一法交叉验证 （leave-one-out cross validation） 。

最后总结一下，尽管我们介绍了用于选择模型的不同版本的交叉验证方法，这些方法也可以用于评估单一模型或算法。例如，如果你实现了一个学习算法并且想估计该算法在你的应用上表现的有多好，交叉验证法是一个合理的方法。

2 特征选择（Feature Selection ）

一种特殊的模型选择方法被称为特征选择。想象一下有一个监督学习问题，其特征数$n$非常大（也许$n\gg m$），但是你怀疑只有一部分特征和学习任务“相关”。

在这样的背景下，你就可以使用特征选择算法来减少特征的数量。给定$n$个特征，有$2^n$中可能的特征子集，那么特征选择问题看成一个在$2^n$个可能模型上的模型选择问题。当$n$很大的时候，遍历比较全部$2^n$个模型成本太大，所以典型的启发式搜索算法是找到一个比较好的特征子集。下面一个搜索算法被称为前向搜索：

  • 1.初始化$\mathcal F= \varnothing$

  • 2.重复{

    • (a)对于$i=1,…,n$，如果$i\notin \mathcal F$，令$\mathcal F_i= \mathcal F \bigcup \{i\}$，然后使用某个版本的交叉验证来评估特征$\mathcal F_i$（即仅使用$\mathcal F_i$中的特征来训练学习算法，然后估计泛化误差）
    • (b)令$\mathcal F$为步骤(a)中得到的最好特征子集

    }

  • 3.选择并输出整个训练过程中得最好的特征子集

外层循环可以在或者$\mathcal F= \{1,..,n\}$，或者$|\mathcal F|$达到预先设定的阈值时停止。

上述算法是一种包装器特征选择 （wrapper model feature selection ）的实例，因为该算法本身就是将学习算法进行“打包”的过程，然后重复调用学习算法来评估不同特征子集的效果。除了前向搜索算法，还有其他搜索算法可以使用。例如反向搜索算法，该算法从$\mathcal F= \{1,..,n\}$开始，每次删除一个特征（利用类似前向搜索中评估增加单一特征的方法来评估单一特征删除），重复该操作直到$\mathcal F =\varnothing$

包装器特征选择通常效果很好，但是计算成本很大，因为要对学习算法多次调用。事实上，完成前向搜索（终止直至$\mathcal F= \{1,..,n\}$）将需要大约调用$O(n^2)$次算法。

过滤器特征选择（Filter feature selection methods） 给出一个启发性，但是计算成本更小的选择特征子集的方式。这里的想法是计算某些简单的分值$S(i)$，该分值可以衡量每个特征$x_i$对分类标签$y$提供了多少信息。然后，我们选择$k$个分值$S(i)$最大的特征。

一种可能定义分值$S(i)$的方法是$x_i$和$y$的相关系数，可以由训练样本计算出。这会导致我们选择和分类标签相关性最强的特征。实际中，我们更多地（尤其是特征$x_i$离散的情形）选择$S(i)$为$x_i$和$y$的互信息（mutual information ）$\text{MI}(x_i,y)$：

（上述等式假设$x_i,y$为二值变量；更一般的，求和会遍历$x_i,y$的取值。）$p(x_i,y),p(x_i),p(y)$可以从训练集中的经验分布中估计出来。

为了获得该分值作用的直观印象，注意互信息可以表达为$\text{KL}-$散度：

$\text{KL}-$散度度量了两个概率分布$p(x_i,y)$和$p(x_i)p(y)$的不同，如果$x_i,y$为独立随机变量，那么这两个分布的$\text{KL}-$散度为$0$。这也符合直观印象：如果$x_i,y$独立，那么$x_i$对$y$没有提供信息。相反，如果$x_i$对$y$提供很多信息，那么$\text{MI}(x_i,y) $应该很大。

最后一个细节：现在根据分值$S(i)$对特征进行排序，你将如何选择特征数量$k$？一个标准的方法是使用交叉验证从可能的不同$k$中进行选择。例如，当应用朴素贝叶斯方法进行文本分类，词汇量$n$通常很大，使用该方法选择特征子集通常可以提高分类精度。